package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode368 {

    public static void main(String[] arg0) {
        int[] nums = new int[]{3, 17};

        // 排序
        Arrays.sort(nums);


        // 方法1，这种方式会超时
//        List<List<Integer>> resList = new ArrayList<>();
//        for (int curr : nums) {
//            boolean needCreate = true;
//            List<List<Integer>> tempList = new ArrayList<>();
//            for (int j = 0; j < resList.size(); j++) {
//                List<Integer> currRes = resList.get(j);
//                int last = currRes.get(currRes.size() - 1);
//                if (curr % last == 0) {
//                    currRes.add(curr);
//                    needCreate = false;
//                } else if (currRes.size() >= 2 && curr % currRes.get(currRes.size() - 2) == 0) {
//                    List<Integer> newRes = new ArrayList<>(currRes);
//                    newRes.remove(currRes.size() - 1);
//                    newRes.add(curr);
//                    tempList.add(newRes);
//                    needCreate = false;
//                }
//            }
//            if (tempList.size() > 0) {
//                resList.addAll(tempList);
//            }
//
//            if (needCreate) {
//                List<Integer> newRes = new ArrayList<>();
//                newRes.add(curr);
//                resList.add(newRes);
//            }
//        }
//
//        int maxLength = 0;
//        List<Integer> res = new ArrayList<>();
//        for (int i = 0; i < resList.size(); i++) {
//            List<Integer> currRes = resList.get(i);
//            System.out.println("res-" + i + ": " + Arrays.toString(currRes.toArray()));
//            if (currRes.size() < 2) {
//                continue;
//            }
//            if (currRes.size() > maxLength) {
//                maxLength = currRes.size();
//                res = currRes;
//            }
//        }


        // 方法2，题解的动态规划
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int maxSize = 1;
        int maxVal = nums[0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            if (dp[i] > maxSize) {
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = len - 1; i >= 0; i--) {
            if (dp[i] == maxSize && maxVal % nums[i] == 0) {
                res.add(nums[i]);
                maxVal = nums[i];
                maxSize --;
            }
        }

        System.out.println("res: " + Arrays.toString(res.toArray()));

    }

}
